import random
import math

def distance(element,centre,cube,table, dimension):
	#calcul de la distance entre un centre de gravite et un element
	A = float(cube[table][dimension][element])
	B = float(centre)
	d =math.sqrt(math.pow((A-B),2))
	return d

def calculCentres(population,tab,gravites,cube, table, dimension):
	#calcul le centre de gravite de chaque groupe de la population
	for index in range(len(gravites)): 
		somme = 0
		for item in tab[index]:
			somme +=  float(cube[table][dimension][item])
		gravites[index] = somme / len(tab[index])

def assignation(gravites,tab,population,cube, table, dimension):
	#attribue chaque element de la population a un des centres de gravite
	for element in  population:
		min 		=1000000000
		index 	= 0
		i 		= 0
		for centre in gravites:  
			d = distance(element,centre,cube, table, dimension)
			if d < min:
				min = d
				i = index
			index+=1
		tab[i].append(element)

def compute(population, nbClusters, nbIter, cube, table, dimension):
	# partitionne la population en nbCluster selon le critere dimension
	gravites=[]
	m=0
	while m <nbClusters:
		trouve=False
		while trouve==False:
			g=random.sample(population,  1)
			G=cube[table][dimension][g[0]]
			present=False
			for n in range (len(gravites)):
				if gravites[n]==G:
					present=True
			if present==False:
				gravites.append(G)
				m=m+1
				trouve=True
	for i in range(nbIter):
		tab = [ [] for x in range(nbClusters) ]
		assignation(gravites,tab,population,cube, table, dimension)
		calculCentres(population,tab,gravites,cube, table, dimension)
	return tab
		
